package daily.year2024.m10;

/**
 * 137.只出现一次的数字II
 *
 * @author wjs 2024/10/20
 */
public class d20 {
    //解法一：计算每一个二进制位的值，进而还原出原本的数字
    class Solution1 {
        public int singleNumber(int[] nums) {
            int[] tmp = new int[32];
            for(int i=0;i < nums.length;i++) {
                for(int j=0;j < 32;j++) {
                    tmp[j] += (nums[i] >>> j) & 1;
                }
            }
            int res = 0;
            for(int i=0;i < 32;i++) {
                res += (tmp[i] % 3) << i;
            }
            return res;
        }
    }

    //解法二：解法一的空间优化版，只需要调换一下循环的先后顺序，就能节省一点空间
    class Solution2 {
        public int singleNumber(int[] nums) {
            int res = 0;
            for(int j=0;j < 32;j++) {
                int tmp = 0;
                for(int i=0;i < nums.length;i++) {
                    tmp += (nums[i] >>> j) & 1;
                }
                res += (tmp % 3) << j;
            }
            return res;
        }
    }
}
